package com.eusun.design.algorithm.demo3;

// Java program for the above approach

import java.util.ArrayList;

//Print all root to leaf paths of an N-ary tree
class NAryTree {

    // Strcuture of an N ary tree node
    static class Node {
        int data;
        ArrayList<Node> child;

        // Parameterized Constructor
        public Node(int x) {
            this.data = x;
            this.child = new ArrayList<>();
        }
    }

    // Function to print the root to leaf
    // path of the given N-ary Tree
    static void printPath(ArrayList<Integer> vec) {

        // Print elements in the vector
        for (int ele : vec) {
            System.out.print(ele + " ");
        }
        System.out.println();
    }

    // Utility function to print all
    // root to leaf paths of an Nary Tree
    static void printAllRootToLeafPaths(Node root, ArrayList<Integer> vec) {

        // If root is null
        if (root == null)
            return;

        // Insert current node's
        // data into the vector
        vec.add(root.data);

        // If current node is a leaf node
        if (root.child.isEmpty()) {

            // Print the path
            printPath(vec);

            // Pop the leaf node
            // and return
            vec.remove(vec.size() - 1);
            return;
        }

        // Recur for all children of
        // the current node
        for (int i = 0; i < root.child.size(); i++)

            // Recursive Function Call
            printAllRootToLeafPaths(root.child.get(i), vec);
        vec.remove(vec.size() - 1);
    }

    // Function to print root to leaf path
    static void printAllRootToLeafPaths(Node root) {

        // If root is null, return
        if (root == null)
            return;

        // Stores the root to leaf path
        ArrayList<Integer> vec = new ArrayList<>();

        // Utility function call
        printAllRootToLeafPaths(root, vec);
    }

    // Driver Code
    public static void main(String[] args) {

        // Given N-Ary tree
        Node root = new Node(1);
        (root.child).add(new Node(2));
        (root.child).add(new Node(3));
        (root.child.get(0).child).add(new Node(4));
        (root.child.get(1).child).add(new Node(5));
        (root.child.get(1).child).add(new Node(6));
        (root.child.get(1).child.get(1).child).add(new Node(7));
        (root.child.get(1).child.get(1).child).add(new Node(8));

        // Function Call
        printAllRootToLeafPaths(root);
    }
}

// This code is contributed by sanjeev2552
